The present invention relates generally to computerized optimization techniques and more specifically to techniques based on a genetic model.
Due to the large number of variables involved, some optimization problems have an exceedingly large solution space. For example, selecting design parameters such as size and threshold voltage for each of thousands of instances (i.e., gates) in an integrated circuit to minimize power consumption while maintaining acceptable timing performance is such a problem.
One approach to solving complex optimization problems is genetic optimization, an iterative, computer-implemented technique in which candidate solutions are generated using a genetic model. The genetic model typically includes a set of N randomly generated chromosomes, each chromosome comprising a number of genes. Since each gene represents a particular state of a parameter to be optimized in one part of a system (e.g., the size of one instance in an integrated circuit), each chromosome represents a possible solution to the global optimization problem. In a typical application, the configuration specified by each chromosome is evaluated, and a figure of merit or xe2x80x9cscorexe2x80x9d is assigned to each chromosome. For example, in the case of an integrated circuit design, a circuit having the characteristics of each chromosome may be simulated to assign a score indicating the desirability of its power consumption and timing performance. Once each chromosome has been assigned a score, the N chromosomes may be xe2x80x9cmatedxe2x80x9d or xe2x80x9cmutatedxe2x80x9d in various ways to create other potential solutions or xe2x80x9cchildren,xe2x80x9d which may, in turn, be evaluated and assigned a score. If a child has a higher score than one of the original N chromosomes, the chromosome with the lowest score may be discarded. Eventually, the candidate solutions generated in this fashion may converge to the global optimum.
A key aspect of such a genetic algorithm is reproduction, the method by which new solutions are generated during each xe2x80x9cmating season.xe2x80x9d In one well-known approach, pairs of chromosomes or xe2x80x9cmating combinationsxe2x80x9d are formed, and mating combinations are randomly selected for possible mating. If the composite score of a mating combination is higher than a predetermined threshold, the chromosomes are mated. Otherwise, they are not mated. However, this approach can lead to too many or too few children being produced during each mating season, if the threshold is set too high or too low. The consequence in either case is slower convergence.
It is thus apparent that there is a need in the art for an improved method and system for reproduction in a genetic optimization process.
A method is provided for reproduction in a computer-implemented optimization process based on a genetic model. Both a system and a computer-readable storage medium containing program instructions are provided for carrying out the method.
Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.